package core;

import java.util.Iterator;

public class ScalingFordFulkerson {
	
	public static MaxFlowSolver getSolver() {
		return new MaxFlowSolver() {
			@Override public double solve(final SimpleGraph the_graph) {
				return new ScalingFordFulkerson().getMaxFlow(the_graph);
			}
			@Override public String getName() {return "Scaling Ford Fulkerson";}
		};
	}
	
	public double getMaxFlow(SimpleGraph graph){
		double maxFlow = 0;
		// Initate a flow graph with edges having capacity >= delta
		FlowGraph flowGraph = new FlowGraph(graph);

		// Get delta of Graph
		double delta = getDelta(graph, flowGraph.getSource());
		
		while(delta >= 1){
			// find s-t path
			flowGraph.unVisitEdges();
			Path path = SearchPath.getPath(flowGraph, flowGraph.getSource(), flowGraph.getSink(), new Path(), delta-1);
			while(path.size() > 0) {
				// if path found agument path and increment flow
				maxFlow += flowGraph.augment(path);
				flowGraph.unVisitEdges();
				// Update the flow in the residual graph
				path = SearchPath.getPath(flowGraph, flowGraph.getSource(), flowGraph.getSink(), new Path(), delta-1);
			}
			// otherwise divide delta by 2
			delta /= 2;
		}
		System.out.println(flowGraph);
		return maxFlow;
	}
	
	public static double getDelta(SimpleGraph graph, Vertex from) {
		@SuppressWarnings("unchecked")
		Iterator<Edge> egdesIterator = graph.incidentEdges(from);
		double maxCapacity = 0;
		double delta = 1;
		while (egdesIterator.hasNext()) {
			double currentEdgeCapacity = (Double)egdesIterator.next().getData(); 
			maxCapacity = Math.max(maxCapacity, currentEdgeCapacity);
		}

		while (delta * 2 <= maxCapacity) {
			delta *= 2;
		}

		return delta;
	}

	public static void main(String[] args) throws Exception {
		SimpleGraph graph;
		graph = new SimpleGraph();
		GraphInput.LoadSimpleGraph(graph, args[0]);
		ScalingFordFulkerson scalingFordFulkerson = new ScalingFordFulkerson();
		double maxFlow = scalingFordFulkerson.getMaxFlow(graph);
		System.out.println(maxFlow);
	}
}
